1. Field of the Invention
The invention relates generally to the field of multiply accumulate modules. More specifically, the invention is directed towards a Booth encoding circuit within a multiplier of a multiply-accumulate module.
2. Description of Related Art
Known digital systems may multiply two binary numbers, a multiplier binary number and a multiplicand binary number, in a manner similar to the multiplication of two decimal numbers. Specifically, such systems may examine successive bits of the multiplier, beginning with the least significant bit of the multiplier. When the examined multiplier bit is a a multiplicand binary number is copied in its entirety to produce partial products. When the multiplier bit is a “0,” zeros are copied to produce partial products. Moreover, the total number of copied zeros is equivalent to the number of bits of the multiplicand binary number. The partial products in successive lines then may be shifted one position to the left relative to the previous line. When all of the multiplier bits have been examined, the partial products in successive vertical lines are summed to produce the resultant product of the multiplier binary number and the multiplicand binary number. Nevertheless, in order to complete the multiplication process, the above-described multiplication process generates a partial product for each multiplier bit.
Some known digital signal processors (DSP's) may be equipped with a multiply-accumulate module for the execution of such multiplication of the multiplier and the multiplicand. The speed of the multiply-accumulate module may affect the operation frequency of the DSP, such that increasing the speed of the multiply-accumulate module also may increase the operation frequency of the DSP. Some known multiply-accumulate modules may include a multiplier. In some known multiply-accumulate modules, the multiplier may account for about half of the delay in the critical path of the multiply-accumulate module. Consequently, increasing the speed the multiplier substantially may increase the overall speed of the multiply-accumulate module.
In order to decrease the number of partial products generated during the multiplication of the multiplier binary number and the multiplicand binary number, some known multipliers may employ a Booth encoding algorithm or method. Reducing the number of partial products may increase the speed of the multiplier. In order to reduce the number of partial products, a known Booth encoding algorithm may recode a radix-2 multiplier Y into a radix-4 multiplier Z with an encoded digital set, {−2, −1, 0, 1, 2}, such that the number of partial products may be reduced by one half.
A Booth encoding circuit may be designed to employ such a Booth encoding algorithm. Referring to FIG. 1, a known Booth encoding circuit 100 is shown. Booth encoding circuit 100 may comprise a plurality of cells 102a-102d and a plurality of inputs Y2n, Y2n+1, and Y2n−1, which may be the 2nth, 2nth+1, and 2nth−1 bits of a multiplier Y, respectively. Inputs Y2n and Y2n−1 each may be connected to cells 102b and 102c, and input Y2n−1 may be connected to cells 102a, 102c, and 102d. Cell 102c may comprise a first switch 103a and a second switch 103b, each of which may be connected to an input of a NAND gate 104. An output of NAND gate 104 then may be connected to an output inverter 106 of cell 102c, such that the output of cell 102c is located at node 1. In addition, the output of inverter 106 may be indirectly connected to a Booth encoding circuit 100 output inverter 108, such that the output of Booth encoding circuit 100 is located at a node 2.
Moreover, Booth encoding circuit 100 also comprises a plurality of transistor paths between each of the inputs and the output of Booth encoding circuit 100. A path is defined herein as the electrical route over which a particular input signal must travel in order to reach the output of a Booth encoding circuit. A transistor stage level for a particular path is defined herein as the number of transistors through which an input flows in order to reach the output of a Booth encoding circuit. Booth encoding circuit 100 further may comprise at least one “critical transistor stage path,” which is defined herein as the path or paths having the greatest transistor stage level between an input and the output of Booth encoding circuit 100.
In Booth encoding circuit 100, the critical path flows through cell 102c, such that the critical path comprises NAND gate 104 and inverter 106. The output signal of inverter 106 maybe logically expressed as inverter 106 output=(Y2n+1⊕Y2n)*{overscore ((Y2n−1⊕Y2n))}, where ⊕ is the logic symbol for an exclusive OR (XOR) logic gate, * is the logic symbol for an AND logic gate, and the bar is the logic symbol for NOT. Moreover, because NAND gate 104 is connected between inverter 106 and each of switches 103a and 103b, NAND gate 104 drives inverter 106 at least for the critical path of Booth encoding circuit 100. In addition, NAND gate 104 is cascaded with a plurality of p-channel transistors and a plurality of n-channel transistors, such as transistors 110a-110h. Because inverter 106 may drive a number of cells in a Booth decoder circuit (not shown) of the multiplier, as a load capacitance increases, the driving efficiency of cascaded n-channel and p-channel transistors connected to a NAND gate may be reduced, such that the speed of cell 102c also may be reduced.